import Node from './models'

class LinkedList {
  constructor () {
    this.head = null
    this.count = 0
  }

  push (element) {
    // 1. 链表为空
    if (this.head === null) {
      this.head = new Node(element)
    } else {
      // 2. 链表不为空
      let p = this.head
      while (p.next) {
        p = p.next
      }
      p.next = new Node(element)
    }
    this.count++
  }

  insert (element, index) {
    if (index > this.count || index < 0) {
      throw new Error('target index out of range:' + this.count)
    }
    const node = new Node(element)
    // 头插
    if (index === 0) {
      // 链表为空
      if (this.head === null) {
        this.head = node
      } else {
        node.next = this.head
        this.head = node
      }
      this.count++
    } else if (index === this.count) {
      this.push(element)
    } else {
      // 中间
      let p = this.head
      for (let i = 0; i < index - 1; i++) {
        p = p.next
      }
      node.next = p.next
      p.next = node
      this.count++
    }
  }

  getElementAt (index) {
    if (index > this.count || index < 0) {
      throw new Error('target index out of range:' + this.count)
    }
    let p = this.head
    for (let i = 0; i < index; i++) {
      p = p.next
    }
    return p
  }

  remove (element) {
    const index = this.indexOf(element)
    if (index !== -1) {
      this.removeAt(index)
    }
  }

  indexOf (element) {
    let index = 0
    for (let p = this.head; p !== null; p = p.next) {
      if (p.element === element) {
        return index
      }
      index++
    }
    return -1
  }

  removeAt (index) {
    if (index >= this.count || index < 0) {
      throw new Error('target index out of range:' + this.count)
    }
    // 头位置
    let result
    if (index === 0) {
      result = this.head.next
      this.head = this.head.next
    } else {
      const p = this.getElementAt(index - 1) // 找前驱
      result = p.next
      p.next = p.next.next
    }
    this.count--
    return result.element
  }

  isEmpty () {
    return this.size() === 0
  }

  size () {
    return this.count
  }

  toString () {
    let str = ''
    for (let p = this.head; p !== null; p = p.next) {
      str += p.element + '->'
    }
    str = str + 'null'
    return str
  }
}

export default LinkedList
